
/**
 * 八皇后
 * 
 * @author Everest
 *
 */
public class EightQueen {

	public static final int queenNum = 8;
	public static int totalResult = 0;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		long time = System.currentTimeMillis();
		int[] queens = new int[queenNum];
		for (int i = 0; i < queenNum; i ++ ){
			queens[i] = -1;
		}
		traceBack(queens);
//		recursion(queens, 0);
		System.out.println(totalResult);
		System.out.println(System.currentTimeMillis() - time + "ms");
	}
	
	/**
	 * 递归法
	 * 
	 * @param queens
	 */
	public static void recursion(int[] queens, int col) {
		for (int tmpRow = 0; tmpRow < queenNum; tmpRow ++) {
			if (isSafe(queens, tmpRow, col)) {
				queens[col] = tmpRow;
				if (col == queenNum - 1) {
					printResult(queens);
					totalResult++;
					return;
				}
				recursion(queens, col + 1);
			}
		}
	}
	
	/**
	 * 回塑法
	 * 
	 * @param queens
	 */
	public static void traceBack(int[] queens) {
		int curCol = 0;
		boolean find = false;
		while (curCol >= 0) {
			int tmpRow = queens[curCol] + 1;
			queens[curCol] = -1;
			if (tmpRow >= queenNum) {
				curCol --;
				continue;
			}
			for (; tmpRow < queenNum; tmpRow++) {
				if(isSafe(queens, tmpRow, curCol)) {
					queens[curCol] = tmpRow;
					find = curCol == queenNum - 1;
					curCol++;
					break;
				} else if (tmpRow == queenNum - 1) {
					curCol --;
				}
			}
			
			if (find) {//找到一个解
				printResult(queens);
				totalResult ++;
				curCol --;
				find = false;
			} 
		}
	}

	public static boolean isSafe(int[] queens, int row, int col) {
		if (queens[col] == row) {
			return false;
		}
		int tmpRow;
		for (int tmpCol = 0; tmpCol < col; tmpCol ++) {
			tmpRow = queens[tmpCol];
			if (tmpRow == row) {//同一行
				return false;
			}
//			if (tmpCol == col) {
//				return false;
//			}
			if (tmpCol + tmpRow == col + row || tmpCol - tmpRow == col - row) {
				return false;
			}
		}
		return true;
	}
	
	private static void printResult(int[] queens) {
		for (int i = 0; i < queens.length; i ++) {
			for (int j = 0; j < queens.length; j ++) {
				if (queens[i] == j) {
					System.out.print("Q ");
				} else {
					System.out.print("* ");
				}
			}
			System.out.println();
		}
		System.out.println();
		System.out.println();
	}

}
